package com.zdj;

import java.util.Stack;

/**
 * @author zhangdj
 * @date 2021-10-06 18:50:36
 * 删除不匹配的括号
 */
public class RemoveInvalidParentheses {

    public static final char DEL_FLAG = '#';

    public static void main(String[] args) {
        System.out.println(removeInvalidParentheses2("))(("));
    }

    public static String removeInvalidParentheses(String s) {
        if (s == null || s.length() <= 0) {
            return s;
        }
//        StringBuilder result = new StringBuilder(s);
        // 栈存放左括号的位置信息
        Stack<Integer> stack = new Stack<>();
        // 栈存放右括号的位置信息
        Stack<Integer> indexStack = new Stack<>();
        char[] chars = s.toCharArray();
        for (int j = 0; j < chars.length; j++) {
            char c = chars[j];
            // 左括号入栈
            if (c == '(') {
                stack.push(j);
            }
            // 遇到右括号 栈中有元素说明匹配 并弹出元素
            if (c == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    // 不匹配记录索引位置
                    indexStack.push(j);
                }
            }
        }
        // 替换不匹配的右括号
        for (int k : indexStack) {
            s = replaceCharAt(s, k);
        }
        // 替换不匹配的左括号
        for (int k : stack) {
            s = replaceCharAt(s, k);
        }
        // 替换指定字符为""
        return s.replaceAll(DEL_FLAG + "", "");
    }

    public static String removeInvalidParentheses2(String s) {
        if (s == null || s.length() <= 0) {
            return s;
        }
        StringBuilder result = new StringBuilder(s);
        // 栈存放左括号的位置信息
        Stack<Integer> stack = new Stack<>();
        // 栈存放右括号的位置信息
        Stack<Integer> indexStack = new Stack<>();
        char[] chars = s.toCharArray();
        for (int j = 0; j < chars.length; j++) {
            char c = chars[j];
            // 左括号入栈
            if (c == '(') {
                stack.push(j);
            }
            // 遇到右括号 栈中有元素说明匹配 并弹出元素
            if (c == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    // 不匹配记录索引位置
                    indexStack.push(j);
                }
            }
        }
        // 已经删除字符的个数 每删除一个加1
        int delCount = 0;
        // 删除不匹配的右括号
        for (int k : indexStack) {
            // 删除时 根据已经删除的字符个数索引值相应减少对应的值
            result.deleteCharAt(k - delCount);
            delCount++;
        }
        // 删除不匹配的左括号
        for (int k : stack) {
            result.deleteCharAt(k - delCount);
            delCount++;
        }
        return result.toString();
    }

    public static String replaceCharAt(String s, int pos) {
        char[] chars = s.toCharArray();
        chars[pos] = DEL_FLAG;
        return new String(chars);
    }


    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        StringBuilder build = new StringBuilder();
        boolean[] inArr = new boolean[s.length()];

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
                inArr[i] = true;
            } else if (s.charAt(i) == ')') {
                if (!stack.isEmpty()) {
                    inArr[stack.pop()] = false;
                } else {
                    inArr[i] = true;
                }
            }
        }

        for (int i = 0; i < inArr.length; i++) {
            if (!inArr[i]) build.append(s.charAt(i));
        }
        return build.toString();
    }

}
